#include "AnalizadorDatos.h"
#include "RamificacionYPoda.h"
#include <map>
#include <queue>
#include <list>
#include <vector>
#include <iostream>
#include <utility>
#include <fstream>
#include <cstdlib>
#include <limits.h>
#include <algorithm>


RamPoda::RamPoda(string nombreFichero) : DP(nombreFichero)
{
    ValorInicialDeCota=INT_MAX;
}

DatosProblema* RamPoda::getDatosProblema()
{
    return &DP;
}

void RamPoda::RamPodaSol()
{
    Nodo nodo;
    int numhijos;
    //Conjunto(Nodo) NV;                     //(Cjto de Nodos vivos)(Vector, Lista, Queue)
    //NodoInicial(nodo);                     //(Genera nodo inicial de expansión)(inicializado en constructor)
    Anyadir(nodo);                           //(Inicialización de NV)
    PonerCota(Voraz());                      //(Inicialización de valor de cota)
    //~ PonerCota(INT_MAX);                      //(Inicialización de valor de cota)
    while (!EsVacio())                       //(NV != NULL)  //(Hay nodos vivos)
    {
        nodo = Extraer();                       //(Extrae un nodo y lo elimina de NV)
        numhijos = Expandir(nodo);              //(Expansión)
        DP.incExpansion();
        for (int i=0; i<numhijos; i++)          //(¿Qué hacemos con los hijos?)
        {
            nodo=Extraer();
            if (Aceptable(nodo) && Factible(nodo))   //(Cota y restricciones)
            {
                DP.incUsados();
                if (Solucion(nodo))
                {
                    if (Valor(nodo)<Valor(mejor_sol))
                    {
                       mejor_sol=nodo;
                       PonerCota(Valor(mejor_sol));//(Nueva cota)
                    }
                }
                else
                {
                   ValorDeCota(nodo);
                   Anyadir(nodo); //(guardar para expansión)
                }
            }
            else
            {
                DP.incPoda();
            }
            //Hijos.pop_front();
        }
    }
    mejor_sol.setCota(Valor(mejor_sol));
}


void RamPoda::NodoInicial(Nodo N)
{
    N.setK(0);
}

void RamPoda::PonerCota(int nueva_cota)
{
    DP.setCota(nueva_cota);
}

int RamPoda::Expandir(Nodo N)
{
    int numhijos=0;
    int K=N.getK();
    int Num_elementos=DP.getNum_elementos();
    for(int i=0 ; i<Num_elementos; i++)             //(posibles valores de componente)
    {
        if(i!=K && !N.IsIN(i))
        {
            DP.incNNodo();
            Nodo Nuevo=Nodo(N);
            Nuevo.setK(K+1);
            Nuevo.setNewData(i);
            Nuevo.setCota(ValorDeCota(Nuevo));
            Nuevo.setValor(Valor(Nuevo));
            //~ Nuevo.Muestra();                             //Mostrar Nodos antes de insertar lista nodos vivos
            Anyadir(Nuevo);                              //(copia de nodo)
            numhijos++;
        }
    }
    return(numhijos);
}


bool RamPoda::Aceptable(Nodo N)
{
    switch(DP.getModalidad())
    {
        case 0:
        {
            return true;
            break;
        }
        default:
        {
            return(DP.getCota() >= ValorDeCota(N));
            break;
        }
    }
}


bool RamPoda::Factible(Nodo N)
{
    int pes=0;
    int K=N.getK();
    bool vueltaCero=false;
    vector<int> solucion=N.getSolucion();
    vector<int>::iterator it=solucion.begin();
    for(int i=0; i<K; i++,it++)
    {
        pes+=DP.BuscarValor(i,*it);
    }
    it=solucion.begin();
    for(int i=0; *it<K && i<K && i<(DP.getNum_elementos()-1) && !vueltaCero; i++)
    {
        if(!*it )vueltaCero=true;
        it=*it+solucion.begin();

    }
    return (DP.getCota() >= pes && !vueltaCero);
}


bool RamPoda::Solucion(Nodo N)
{
    return (DP.getNum_elementos()==N.getK());
}

int RamPoda::Valor(Nodo N)
{
    int val=0;
    int K=N.getK();
    if(K!=0)
    {
        vector<int> solucion=N.getSolucion();
        vector<int>::iterator it=solucion.begin();
        for (int i=0; i<K; i++, it++)
        {
            val+=DP.BuscarValor(i,*it);
        }
    }
    else
    {
        val=INT_MAX;    //primera comparacion
    }
    return(val);
}



int RamPoda::ValorDeCota(Nodo N)
{
    int val=0;
    switch(DP.getModalidad())
    {
        case 1:
        {
            int K=N.getK();
            vector<int> solucion=N.getSolucion();
            vector<int>::iterator it=solucion.begin();
            for(int i=0; i<K; i++,it++)
            {
                val+=DP.BuscarValor(i,*it);
            }
            break;
        }
        case 2:
        {
            int K=N.getK();
            int Num_elementos=DP.getNum_elementos();
            vector<int> solucion=N.getSolucion();
            vector<int>::iterator it=solucion.begin();
            for(int i=0; i<K; i++,it++)
            {
                val+=DP.BuscarValor(i,*it);
            }
            for(int i=K; i<Num_elementos; i++)
            {
                int temp=INT_MAX;
                for(int j=0; j<Num_elementos; j++)
                {
                    int peso=DP.BuscarValor(i,j);
                    if(peso!=0 && temp>peso)temp=peso;
                }
                val+=temp;
            }
            break;
        }
        case 3:
        {
           int K=N.getK();
            int Num_elementos=DP.getNum_elementos();
            vector<int> solucion=N.getSolucion();
            vector<int>::iterator it=solucion.begin();
            for(int i=0; i<K; i++,it++)
            {
                val+=DP.BuscarValor(i,*it);
            }
            for(int i=K; i<Num_elementos; i++)
            {
                int temp=INT_MAX;
                for(int j=0; j<Num_elementos; j++)
                {
                    int peso=DP.BuscarValor(i,j);
                    if(j!=K && !N.IsIN(j) && temp>peso)temp=peso;
                }
                val+=temp;
            }
            break;
        }
        default:
        {
            val=INT_MAX;
            break;
        }
    }
    return(val);
}

Nodo RamPoda::getNodo()
{
    return mejor_sol;
}

int RamPoda::Voraz()
{
    Nodo N;
    int Num_elementos=DP.getNum_elementos();
    vector<int> voraz=vector<int>(Num_elementos,-1);
    //~ cout << voraz.size() << endl;
    vector<int>::iterator it;
    vector<int>::iterator sig;
    it=voraz.begin();
    int pos2=0;
    int K=0;
    while(K<Num_elementos)
    {
        int temp=INT_MAX;
        int pos=-1;
        int peso=0;
        for(int i=0 ; i<Num_elementos; i++)             //(posibles valores de componente)
        {
            //~ cout << "i:" << i << "\t";
            if(pos2!=i && !N.IsIN(i))
            {
                sig=voraz.begin()+i;
                if(*sig<0)
                {
                    peso=DP.BuscarValor(pos2,i);
                    if(peso!=0 && temp>peso)
                    {
                        *it=i;
                        temp=peso;
                        pos=i;
                    }
                }
                else if((K+1)==Num_elementos){*it=0;}
            }
        }
        it=voraz.begin()+pos;
        pos2=pos;
        K++;
        //~ cout << endl;
        N.setVector(voraz);
        N.setK(K);
        //~ N.Muestra();
    }

    return(Valor(N));
}


RamPodaVector::RamPodaVector(string nomFich): RamPoda(nomFich)
{

}


void RamPodaVector::Anyadir(Nodo N)
{
    NV.push_back(N);
    stable_sort(NV.begin(),NV.end(), Nodo::menor);
}

Nodo RamPodaVector::Extraer()
{
    Nodo temporal=NV.front();
    NV.erase(NV.begin());
    return temporal;
}

bool RamPodaVector::EsVacio()
{
    return(NV.empty());
}

RamPodaLista::RamPodaLista(string nomFich): RamPoda(nomFich)
{
}


void RamPodaLista::Anyadir(Nodo N)
{
    NV.push_back(N);
    NV.sort(Nodo::menor);
}

Nodo RamPodaLista::Extraer()
{
    Nodo temporal=NV.front();
    NV.pop_front();
    return temporal;
}

bool RamPodaLista::EsVacio()
{
    return(NV.empty());
}



RamPodaQueue::RamPodaQueue(string nomFich): RamPoda(nomFich)
{

}



void RamPodaQueue::Anyadir(Nodo N)
{
    NV.push(N);
}

Nodo RamPodaQueue::Extraer()
{
    Nodo temporal=NV.top();
    NV.pop();
    return temporal;
}

bool RamPodaQueue::EsVacio()
{
    return(NV.empty());
}
